Minimum path sum

Time: O(MxN); Space: O(M+N); medium

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note:

  • You can only move either down or right at any point in time.

Example 1:

Input: grid =

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7

Explanation:

  • Because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum.

Example 2:

Input: grid = [[1,3,2]]

Output: 6

Explanation:

  • Path is: 1 -> 3 -> 2

[2]:

class Solution1(object):
    """
    Time: O(M*N)
    Space: O(M+N)
    """
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        sum = list(grid[0])
        for j in range(1, len(grid[0])):
            sum[j] = sum[j - 1] + grid[0][j]

        for i in range(1, len(grid)):
            sum[0] += grid[i][0]
            for j in range(1, len(grid[0])):
                sum[j] = min(sum[j - 1], sum[j]) + grid[i][j]

        return sum[-1]

[3]:

s = Solution1()

grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
assert s.minPathSum(grid) == 7

grid = [[1,3,2]]
assert s.minPathSum(grid) == 6